

#if 0
#include <string>
#include <iostream>

template <typename T>
void do_thing(T& t) {
	std::cout << same(t) << std::endl;
}

std::string& same(std::string& s) {
	return s;
}

int main() {
	do_thing( std::string("blah") );
}

#else






















#include <string>
#include <vector>
#include <deque>
#include <set>
#include <map>
#include <iterator>
#include <stack>
#include <algorithm>
#include <iostream>
//=====================================================================
//#include <atma/assert.hpp>
//=====================================================================
#include <boost/shared_ptr.hpp>
#include <boost/enable_shared_from_this.hpp>
#include <boost/bind.hpp>
#include <boost/lexical_cast.hpp>
#include <boost/variant.hpp>
#include <boost/tuple/tuple.hpp>
//=====================================================================
#include <sooty2/lexing/input_iterator.hpp>
#include <sooty2/lexing/lexer.hpp>
#include <sooty2/parsing/parseme.hpp>
#include <sooty2/parsing/parsemes.hpp>
#include <sooty2/parsing/parser.hpp>

//#include <sooty2/walking/detail/layout.hpp>
//#include <sooty2/walking/detail/context.hpp>
#include <sooty2/walking/detail/abstract_walker_backend.hpp>
#include <sooty2/walking/walker.hpp>
#include <sooty2/walking/placeholder.hpp>

#include <sooty2/transforming/transformer.hpp>

//#include <sooty2/parsing/detail/parseme_backend.hpp>
#include <sooty2/common/detail/append_success.hpp>
#include <sooty2/common/detail/append_invalid.hpp>

using namespace sooty::lexing;

// here's what we're testing:
//    10.1 is a float
//    10/1 is an integer, fwdslash, integer







void print_identifier(lex_results_t& L) {
	std::cout << "identifier: " << make_string(L.begin, L.end) << std::endl;
}

void print_giraffe(lex_results_t& L) {
	std::cout << "giraffe: " << make_string(L.begin, L.end) << std::endl;
}

using sooty::parsing::parser;

using namespace sooty::lexing;
using namespace sooty::parsing;


//typedef const walking_context_t& walking_context_ref;






using sooty::walking::detail::context_ref;
using sooty::walking::detail::how_to_traverse;


bool traverse(context_ref context, how_to_traverse::Enum htt)
{
	switch (htt)
	{
		case how_to_traverse::dive:
			context.dive();
			break;
			
		case how_to_traverse::surface:
			context.surface();
			break;
			
		case how_to_traverse::next_sibling:
			context.next();
			break;
	}
	
	return true;
}








/*

struct rewrite_setter_walker_backend : abstract_walker_backend
{
	int id;
	
	rewrite_setter_walker_backend(int id) : id(id) {
	}
	
	bool compare_impl(walking_context_ref context) {
		const_cast<walking_context_ref>(context).add_rewriter(id);
		return true;
	}
	
	abstract_walker_backend_ptr clone() {
		return abstract_walker_backend_ptr(new rewrite_setter_walker_backend(*this));
	}
};


struct rewrite_walker_backend : abstract_walker_backend
{
	int id;
	
	rewrite_walker_backend(int id) : id(id) {
	}
	
	bool invalid_when_empty() const {
		return false;
	}
	
	bool compare_impl(walking_context_ref context_c)
	{
		walking_context_ref context = const_cast<walking_context_ref>(context_c);
		
		walking_context_t::rewriter_positions_t::const_iterator i = context.rewriter_positions.find(id);
		if (i == context.rewriter_positions.end())
			return false;
		
		if (&context.container() != i->second.first)
			return false;
		
		context.erase(context.begin() + i->second.second, context.current() + 1);
		//context.erase(
		return true;
	}
	
	abstract_walker_backend_ptr clone() {
		return abstract_walker_backend_ptr(new rewrite_walker_backend(*this));
	}
};

struct parseme_inserter_walker_backend : abstract_walker_backend
{
	int id;
	
	parseme_inserter_walker_backend(int id) : id(id) {
	}
	
	bool invalid_when_empty() const {
		return false;
	}
	
	bool compare_impl(walking_context_ref context_c)
	{
		walking_context_ref context = const_cast<walking_context_ref>(context_c);
		//context.container().push_back( parseme(id) );
		context.insert(parseme(id));
		return true;
	}
	
	abstract_walker_backend_ptr clone() {
		return abstract_walker_backend_ptr(new parseme_inserter_walker_backend(*this));
	}
};

struct variable_inserter_walker_backend : abstract_walker_backend
{
	int id;
	
	variable_inserter_walker_backend(int id) : id(id) {
	}
	
	bool invalid_when_empty() const {
		return false;
	}
	
	bool compare_impl(walking_context_ref context_c)
	{
		walking_context_ref context = const_cast<walking_context_ref>(context_c);
		context.insert( context.stored_variables[id].begin(), context.stored_variables[id].end() );
		return true;
	}
	
	abstract_walker_backend_ptr clone() {
		return abstract_walker_backend_ptr(new variable_inserter_walker_backend(*this));
	}
};





template <int I> struct variable;

struct walker;

struct rewriter
{
private:
	abstract_walker_backend_ptr backend;
public:
	rewriter(const abstract_walker_backend_ptr& backend) : backend(backend) {}
	walker operator [](walker&);
	
	template <int I>
	walker operator [](variable<I>& v);
};




walker rewriter::operator[]( walker& w )
{
	abstract_walker_backend_ptr new_rhs = sooty::common::detail::clone_tree(w.backend);
	abstract_walker_backend_ptr new_lhs(new rewrite_setter_walker_backend(0));
	sooty::common::detail::append_success(new_lhs, link_t(this->backend, how_to_traverse::stay) );
	sooty::common::detail::append_success(new_lhs, link_t(abstract_walker_backend_ptr(new rewrite_walker_backend(0)), how_to_traverse::stay));
	sooty::common::detail::append_success(new_lhs, link_t(w.backend, how_to_traverse::stay) );
	return walker(new_lhs);
}

template <int I>
walker rewriter::operator[]( variable<I>& v ) {
	return this->operator []( (walker)v );
}







template <int I>
struct variable 
{
	walker operator = (const walker& rhs) const {
		abstract_walker_backend_ptr new_rhs = sooty::common::detail::clone_tree(rhs.backend);
		sooty::common::detail::append_success(new_rhs, link_t(abstract_walker_backend_ptr(new variable_walker_backend<I>), how_to_traverse::stay));
		return walker(new_rhs);
	}
	
	operator walker() {
		return walker( abstract_walker_backend_ptr(new variable_inserter_walker_backend(I)) );
		//return walker();
	}
};

namespace sooty {
	variable<1> _1;
	variable<2> _2;
}

template <int I>
struct variable_walker_backend : abstract_walker_backend
{
	bool compare_impl(walking_context_ref context) {
		const_cast<walking_context_ref>(context).stored_variables[I].clear();
		const_cast<walking_context_ref>(context).stored_variables[I].push_back(const_cast<parseme&>(*context.current()));
		return true;
	}
	
	abstract_walker_backend_ptr clone() {
		return abstract_walker_backend_ptr(new variable_walker_backend(*this));
	}
};


walker mk(int id) {
	return walker( abstract_walker_backend_ptr(new parseme_inserter_walker_backend(id)) );
}
*/
//walker rewrite(const walker& lhs, const walker& rhs)
//{
//	static int guid = 0;
//	
//	abstract_walker_backend_ptr new_lhs = sooty::common::detail::clone_tree(lhs.backend);
//	
//	rewrite_setter_walker_backend* blah = new rewrite_setter_walker_backend(guid);
//	rewrite_walker_backend* blah2 = new rewrite_walker_backend(guid);
//	
//	++guid;
//}













using namespace sooty::walking;





void make_lexeme(lexemes& out, lexeme_t::id_t id, lex_results_t& results) {
	out.push_back( lexeme_t(id, results.begin, results.end, position_t()) );
}




static sooty::walking::placeholder<1> _p1;
static sooty::walking::placeholder<2> _p2;


bool walk(parsemes_t& these, const walker& with)
{
	sooty::walking::detail::abstract_walker_backend_ptr current_walker = with.backend;
	sooty::walking::detail::context_t context(these);
	
	while (current_walker)
	{
		if (current_walker->invalid_when_empty() && context.invalid()) {
			if (current_walker->on_invalid.node) {
				traverse(context, current_walker->on_invalid.traversal);
				current_walker = current_walker->on_invalid.node;
			}
			else {
				return false;
			}
		}
		else if ( current_walker->compare_impl(context) )
		{
			traverse(context, current_walker->on_success.traversal);
			current_walker = current_walker->on_success.node;
		}
		else if (current_walker->on_failure.node)
		{
			traverse(context, current_walker->on_failure.traversal);
			current_walker = current_walker->on_failure.node;
		}
		else {
			return false;
		}
	}
	
	return true;
}

int main()
{
	/*char* giraffe = new char[7];
	strcpy(giraffe, "giraffe");
	reverse(giraffe, 7);
	std::cout << giraffe << std::endl;*/
	
	
	

	using sooty::parsing::parseme;
	using sooty::parsing::match;
	
	parser p = match(6) [ match(7) >> match(8) ];
	
	std::string whoo = "whoo";
	
	lexemes test_lexemes;

	
	{
		lexer giraffe = string_("giraffe");
		lexer zebra = string_("zebra");
		lexer identifier = in_range('a', 'z') >> *in_range('a', 'z');
		lexer whitespace = char_(' ');
		//lexer 
		lexer test
			= *(giraffe[boost::bind(make_lexeme, boost::ref(test_lexemes), 6, _1)]
			| identifier[boost::bind(make_lexeme, boost::ref(test_lexemes), 7, _1)]
			| zebra[boost::bind(make_lexeme, boost::ref(test_lexemes), 8, _1)]
			| whitespace)
			;
		
		std::string test_string = "giraffe elephant zebra";
		lex_results_t results = lex(test, test_string.begin(), test_string.end());
		
		std::string result_string = make_string(results.begin, results.end);
		
		sooty::parsing::parsemes_t resultant_parsemes = parse(p, test_lexemes.begin(), test_lexemes.end());
		
		//using sooty::_1;
		
		walker wtest = +eq(4) >> eq(7);
		
		walker w =
			_p1 = eq(6) [
				_p2 = eq(7),
				*eq(8)
			]
			.rewrite [
				sooty::transforming::mk(23) [
					sooty::transforming::mk(40),
					_p2
				]
			]
			;
		
		walk(resultant_parsemes, w);
	}
	
}



/*
walker rewrite_multiplication =
	eq(mult) [
		_1 = eq(term),
		_2 = eq(term)
	]
	.rewite [
		mk(shift) [
			_2,
			mk( log2(_1) )
		]
	]
*/

#endif